/*
 * Copyright (c) 2003, Oracle and/or its affiliates. All rights reserved.
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */

package com.sun.corba.se.impl.orbutil.graph;

import java.util.Collection;
import java.util.AbstractSet;
import java.util.Iterator;
import java.util.Map;
import java.util.HashMap;
import java.util.Set;
import java.util.HashSet;

public class GraphImpl extends AbstractSet implements Graph {
    private Map /* Map<Node,NodeData> */ nodeToData;

    public GraphImpl() {
        nodeToData = new HashMap();
    }

    public GraphImpl(Collection coll) {
        this();
        addAll(coll);
    }

/***********************************************************************************/
/************ AbstractSet implementation *******************************************/
    /***********************************************************************************/

    // Required for AbstractSet
    public boolean add(Object obj) // obj must be a Node
    {
        if (!(obj instanceof Node))
            throw new IllegalArgumentException("Graphs must contain only Node instances");

        Node node = (Node) obj;
        boolean found = nodeToData.keySet().contains(obj);

        if (!found) {
            NodeData nd = new NodeData();
            nodeToData.put(node, nd);
        }

        return !found;
    }

    // Required for AbstractSet
    public Iterator iterator() {
        return nodeToData.keySet().iterator();
    }

    // Required for AbstractSet
    public int size() {
        return nodeToData.keySet().size();
    }

    /***********************************************************************************/

    public NodeData getNodeData(Node node) {
        return (NodeData) nodeToData.get(node);
    }

    private void clearNodeData() {
        // Clear every node
        Iterator iter = nodeToData.entrySet().iterator();
        while (iter.hasNext()) {
            Map.Entry entry = (Map.Entry) iter.next();
            NodeData nd = (NodeData) (entry.getValue());
            nd.clear();
        }
    }

    interface NodeVisitor {
        void visit(Graph graph, Node node, NodeData nd);
    }

    // This visits every node in the graph exactly once.  A
    // visitor is allowed to modify the graph during the
    // traversal.
    void visitAll(NodeVisitor nv) {
        boolean done = false;

        // Repeat the traversal until every node has been visited.  Since
        // it takes one pass to determine whether or not each node has
        // already been visited, this loop always runs at least once.
        do {
            done = true;

            // Copy entries to array to avoid concurrent modification
            // problem with iterator if the visitor is updating the graph.
            Map.Entry[] entries =
                    (Map.Entry[]) nodeToData.entrySet().toArray(new Map.Entry[0]);

            // Visit each node in the graph that has not already been visited.
            // If any node is visited in this pass, we must run at least one more
            // pass.
            for (int ctr = 0; ctr < entries.length; ctr++) {
                Map.Entry current = entries[ctr];
                Node node = (Node) current.getKey();
                NodeData nd = (NodeData) current.getValue();

                if (!nd.isVisited()) {
                    nd.visited();
                    done = false;

                    nv.visit(this, node, nd);
                }
            }
        } while (!done);
    }

    private void markNonRoots() {
        visitAll(
                new NodeVisitor() {
                    public void visit(Graph graph, Node node, NodeData nd) {
                        Iterator iter = node.getChildren().iterator(); // Iterator<Node>
                        while (iter.hasNext()) {
                            Node child = (Node) iter.next();

                            // Make sure the child is in the graph so it can be
                            // visited later if necessary.
                            graph.add(child);

                            // Mark the child as a non-root, since a child is never a root.
                            NodeData cnd = graph.getNodeData(child);
                            cnd.notRoot();
                        }
                    }
                });
    }

    private Set collectRootSet() {
        final Set result = new HashSet();

        Iterator iter = nodeToData.entrySet().iterator();
        while (iter.hasNext()) {
            Map.Entry entry = (Map.Entry) iter.next();
            Node node = (Node) entry.getKey();
            NodeData nd = (NodeData) entry.getValue();
            if (nd.isRoot())
                result.add(node);
        }

        return result;
    }

    public Set /* Set<Node> */ getRoots() {
        clearNodeData();
        markNonRoots();
        return collectRootSet();
    }
}
